1. Field of the Invention
The present invention relates to digital computing, and more particularly to an apparatus and method for implementing carry-look-ahead logic in an N-NARY adder gate.
2. Description of the Related Art
Traditional Binary Addition
In most computer systems, addition and subtraction of numbers is supported. In systems using traditional binary logic, the truth table for one-bit addition is set forth in Table 1.
TABLE 1 A B A + B 0 0 0 0 1 1 1 0 1 1 1 0*
In the last row of Table 1, a carry condition occurs. That is, the result is 0, but a carry into the next-higher-order bit position, corresponding to a decimal value of 2, has conceptually occurred.
In addition to single bits, the addition operation may be performed on multiple bits, including addition of two two-bit values. The truth table for such an operation is set forth in Table 2, where the first operand A is a two-bit value comprising bits A.sub.0 and A.sub.1. The second operand, B, is a two-bit value comprising bits B.sub.0 and B.sub.1.
TABLE 2 A = B = A + B = Decimal Decimal Dec. A.sub.1 A.sub.0 B.sub.1 B.sub.0 Value Value A + B Value 0 0 0 0 0 0 00 0 0 0 0 1 0 1 01 1 0 0 1 0 0 2 10 2 0 0 1 1 0 3 11 3 0 1 0 0 1 0 01 1 0 1 0 1 1 1 10 2 0 1 1 0 1 2 11 3 0 1 1 1 1 3 00* 0 1 0 0 0 2 0 10 2 1 0 0 1 2 1 11 3 1 0 1 0 2 2 00* 0 1 0 1 1 2 3 01* 1 1 1 0 0 3 0 11 3 1 *1 0 1 3 1 00* 0 1 1 1 0 3 2 01* 1 1 1 1 1 3 3 10* 2
Each output value in the "A+B" column of value in Table 2 indicated with an asterisk denotes a carry condition where a one has conceptually carried into the next-higher-order bit (the bit position corresponding to a decimal value of four).
N-NARY Logic
The N-NARY logic family supports a variety of signal encodings, including 1-of-4. The N-NARY logic family is described in a copending patent application, U.S. patent application Ser. No. 09/019,355, filed Feb. 5, 1998, now U.S. Pat. No. 6,066,965, and titled "Method and Apparatus for a N-NARY logic Circuit Using 1-of-4 Encoding", which is incorporated herein for all purposes and is hereinafter referred to as "The N-NARY Patent." In 1-of-4 encoding, four wires are used to indicate one of four possible values. In contrast, traditional static design uses two wires to indicate four values, as is demonstrated in Table 2. In Table 2, the A.sub.0 and A.sub.1 wires are used to indicate the four possible values for operand A: 00, 01, 10, and 11. The two B wires are similarly used to indicate the same four possible values for operand B. "Traditional" dual-rail dynamic logic also uses four wires to represent two bits, but the dual-rail scheme always requires two wires to be asserted. In contrast, N-NARY logic only requires assertion of one wire. The benefits of N-NARY logic over dual-rail logic, such as reduced power and reduced noise, should be apparent from a reading of The N-NARY Patent.
All signals in N-NARY logic, including 1-of-4, are of the 1-of-N form where N is any integer greater than one. A 1-of-4 signal requires four wires to encode four values (0-3 inclusive), or the equivalent of two bits of information. More than one wire will never be asserted for a 1-of-N signal. Similarly, N-NARY logic requires that a high voltage be asserted for all values, even 0. As illustrated in this specification and more thoroughly discussed in the N-NARY Patent, a 1 of N signal is used to convey multiple values of information in an integrated circuit. The 1 of N signal can convey information to and from an N-NARY logic circuit where an N-NARY logic circuit comprises a shared logic tree circuit that evaluates one or more 1 of N input signals and produces a 1 of N output signal. A single 1 of N signal comprises a bundle of N wires routed together between different cells (or different logic circuits) within a semiconductor device. A 1 of N signal uses a 1 of N encoding to indicate multiple values of information conveyed by the bundle of wires of the 1 of N signal where at most one and only one wire of the bundle of wires of the 1 of N signal is true during an evaluation cycle. The present invention further provides that the bundle of N wires may comprise a number of wires from the following group: a bundle of 3 wires, a bundle of 4 wires, a bundle of 8 wires, or a bundle of N wires. Additionally, the present invention may comprise a not valid value where zero wires of the bundle of N wires is active. Further, the present invention provides that the 1 of N encoding on the bundle of N wires cooperatively operate to reduce the power consumption in the integrated circuit according to the number of wires in the bundle of N wires evaluating per bit of encoded information.
Any one N-NARY gate may comprise multiple inputs and/or outputs. In such a case, a variety of different N-NARY encodings may be employed. For instance, consider a gate that comprises two inputs and two outputs, where the inputs are a 1-of-4 signal and a 1-of-2 signal and the outputs comprise a 1-of-4 signal and a 1-of-3 signal. Various variables, including P, Q, R, and S, may be used to describe the encoding for these inputs and outputs. One may say that one input comprises 1-of-P encoding and the other comprises 1-of-Q encoding, wherein P equals two and Q equals four. Similarly, the variables R and S may be used to describe the outputs. One might say that one output comprises 1-of-R encoding and the other output comprises 1-of-S encoding, wherein R equals four and S equals 3. Through the use of these, and other, additional variables, it is possible to describe multiple N-NARY signals that comprise a variety of different encodings.